package ljl.alg.jianzhioffer.round3.easy;

import commons.TreeNode;

public class _68_lowestCommonAncestor {

    class common {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode t = root;
            while (true) {
                if (t.val > p.val && t.val > q.val)
                    t = t.left;
                else if (t.val < p.val && t.val < q.val)
                    t = t.right;
                else
                    return t;
            }
        }
    }

    class better {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (p.val < q.val)
                return lowestCommonAncestor(root, q, p);
            while (root != null) {
                if (root.val > p.val)
                    root = root.left;
                else if (root.val < q.val)
                    root = root.right;
                else
                    break;
            }
            return root;
        }
    }

    class recursive {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root.val > p.val && root.val > q.val)
                return lowestCommonAncestor(root.left, p, q);
            if (root.val < p.val && root.val < q.val)
                return lowestCommonAncestor(root.right, p, q);
            return root;
        }
    }
}
